In today's networks and telecommunication systems, data is typically encapsulated into data messages or packets before transmission. A sending system, for example, may formulate one or more data messages and transmit them across the network. A designated receiving system receives the data messages and extracts the encapsulated data. During transmission, however, errors can be introduced into the data encapsulated in the data message causing the data to be corrupted. Also, the receiving system may erroneously interpret the transmission errors in the data as valid data. Accordingly, transmission error control has become an integral part of any system involved in data communications.
Transmission error control techniques include determining if an error occurred in a received message and discarding the message if an error did occur. One of the more well known transmission error detection techniques is checksum validation. More specifically, a checksum value is calculated for each message and appended to the message before transmission. Upon receiving the message, the receiving system generates its own checksum value for the received message and compares its checksum value to the checksum value in the message. If the checksum values match, then the message is valid and the encapsulated data can extracted and processed. If the checksum values to not match, the receiving system discards the message and requests re-transmission of the message.
FIG. 1 illustrates a block diagram of a conventional checksum generator, generally designated 100. The checksum generator 100 includes an adder 106. The adder 106 receives one word at a time from a message stored in a memory block 102 via line 104. The adder 106 adds the new word with a previous partial sum 110, which is fed back into the adder 106 via line 112. Typically, the partial sum 110 is either initialized to zero, or to a pre-computed partial checksum value. The result of the adder 106 is stored in the partial sum 110 via line 108. The partial sum 110 is a register that is twice as large as the size of the words in the memory block 102. More specifically, the partial sum 110 is 32-bits wide and each word in the memory block 102 is 16-bits wide. Since the partial sum 110 is twice as large as the words added, the sum produced by the adder 106 should not overflow. This eliminates the need for additional circuitry to account for a overflow (carry) resulting from the addition. The adder 106 continues to sequentially add each of the words in the memory block 102 to the previous partial sum 110 until all of the words in the memory block 102 for a particular message have been summed.
The checksum generator 100 passes a sum portion and an overflow portion of the partial sum 110 via lines 116, 114, respectively, to an adder 118. The adder 118 then adds the sum and overflow portions of the partial sum 110 together to produce a sum and possibly an overflow bit. The sum and the overflow bit are passed to the incrementer 122 via line 120. If the overflow bit is set, then the incrementer 122 increments the sum and passes the sum to the inverter 126 via line 124. The inverter 126 then inverts the sum and stores the result as the checksum value 130 via line 128.
The checksum generator 100 has a total delay that is approximately:
                              D          convent                ≈                                                            N                words                            ·                              d                add32                                      r                    +                      d            add16                    +                      d            ovfinv                                              (        1        )            
where Dconvent is the total delay, Nwords is the number of 16-bit words to be checksummed, dadd16 is the delay associated with each 16-bit addition, dadd32 is the delay associated with each 32-bit addition, dovfinv is the delay associated with handling overflow from the final addition and inverting the result, and r is the number of parallel additions that can be performed simultaneously. The total delay Dconvert of the checksum generator 100 is basically a function of the number of words to be checksummed in relation to the types of registers employed. Due to the use of 32-bit adders and the high latency of such addition, the overall calculation is slow. As network throughput requirements are increased, this type of checksum generator and method may reduce network throughput or even cause a bottleneck.
Accordingly, what is needed in the art is a way to reduce the number of high-latency additions that are performed in calculating a checksum.